\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
\usepackage{tikz}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{NAME Jiatu Yan}
\chead{Numerical ODE/PDE Homework \#3}
\rhead{Date 2021.5.9}


\section*{I. Exercise 8.14 Consider approximating $u'\left( x \right) $ at a point $\overline{x}$ using the nearby function values $u\left( \overline{x} \pm h \right) $.}

\subsection*{\small{1. For $u\left( x \right)=\sin\left( x \right)  $ and $\overline{x}=1$, calaculate the errors.}} 

I calculated the errors of the three formulas with c++, the solutions are listed in the following tabular.
\begin{equation*}
	\begin{tabular}{|c |c| c|c|}
		\hline
		$h$&$E_{+}$&$E_{-}$&$E_{0}$\\
		\hline
		$0.01$&$   \frac{u\left( 1+h \right)-u\left( 1 \right)  }{h}-u'\left( 1 \right) \simeq$-4.216325e-03
		    &$\frac{u\left( 1 \right)-u\left( 1 \right)  }{1 - h}-u'\left( 1 \right) \simeq$4.198315e-03
		    &$\frac{u\left( 1+h \right)-u\left( 1-h \right)  }{2h}-u'\left( 1 \right) \simeq$-9.004993e-06\\
		    \hline
		$0.005$&$\frac{u\left( 1+h \right)-u\left( 1 \right)  }{h}-u'\left( 1 \right) \simeq$   -2.105924e-03
		     &$\frac{u\left( 1 \right)-u\left( 1 \right)  }{1 - h}-u'\left( 1 \right) \simeq$ 2.101422e-03
		     &$\frac{u\left( 1+h \right)-u\left( 1-h \right)  }{2h}-u'\left( 1 \right) \simeq$-2.251257e-06\\
		     \hline
	\end{tabular}
\end{equation*}

\subsection*{\small{2. Deduce the orders of accuracy and give a geometric interpretation.}}

We can deduce the orders of accuracy by calculating with the errors we got in the subsection 1 above by
\[
	\mathrm{order} \quad p=\log_2\left( E^{0.01}/E^{0.005}\right)  
.\] 
We have
\begin{equation*}
	\begin{tabular}{|c|c|c|c|}
		\hline
		&$E_{+}$& $E_{-}$& $E_{0}$\\
		\hline
		order&1.00153&0.998445&        1.99999\\
		\hline
	\end{tabular}.
\end{equation*}

Thus we know that the order of accuracy of the first and the second formula are 1, while that of the third one is 2.
We can explain this geometrically.

Firstly we explain the first two formulas.
By the definition of the left and right derivatives and the continuity of 
the function $\sin\left(x  \right) $, we know that the order of accuracy of the two formulas are the same, besides, the coefficients of them are the same. 
Thus without losing generality, we only discuss the second formula.
In the first figure in figure \ref{figure1}, the length of the green line is 
$
	 hE_{-} =  \sin\left( 1 \right)-\sin\left(1-h  \right) - h\cos\left( 1 \right)
$. 
For any straight line whose slope bigger than $\cos\left(1  \right) $ and smaller than $D_{-}u\left(1  \right) $, 
the point B will lie above the line when h becomes small enough. Thus we have $hE_{-}=\mathrm{O}\left( h^2 \right) $, 
i.e., $E_{-}=\mathrm{O}\left(  h\right) $. Similarly we can deduce that $hE_{+} = \mathrm{O}\left( h \right) $.

In the second figure in figure \ref{figure1}, the length of the brown line is $-hE_{+}$ and the green one is $hE_{-}$.
By the definition of $D_{0}u\left(1  \right) $, we have $hE_{0} = \left(hE_{-}-hE_{+}\right)/2$.
Since the order of $hE_{-}$ is the same as that of $hE_{+}$ and they have the same coefficients of the $h^2$ items,
we have $hE_{0} = \left( h^{3} \right) $, i.e., $E_{0}=\mathrm{O}\left( h^2 \right) $.

\begin{figure}[h]
	\centering
	\caption{Figures for $D_{-}u\left( 1 \right) $ and $D_{0}u\left( 1 \right) $}
	\label{figure1}
	\begin{tikzpicture}
		\draw[red] (4, 4) -- (1, 2); 
		\draw[blue] (1, 1) -- (4, 4);
		\draw[blue] (1, 1) -- (4, 1);
		\draw[blue] (4, 1) -- (4, 4);
		\draw (4, 4) -- (1, 1.5);;
		\node[below] at (3, 2) {$\small{kx+sin(1)-1}$};
		\node[right, blue] at (4, 2) {$sin(1) - sin(1-h)$};
		\draw[green] (1, 1) -- (1, 2);
		\node[left, green] at (1, 1.5) {$hE_{-}$};
		\node[above, blue] at (4, 4) {$A(1, sin(1))$};
		\node[below, blue] at (1, 1) {$B(1-h, sin(1-h))$};
		\draw[red] (12, 4) -- (9, 2);
		\draw[blue](9, 1)--(12, 4);
		\draw[blue](12, 4) -- (9, 2.5);
		\draw[blue](9, 2.5) -- (12, 2.5);
		\draw[blue](12, 1) -- (9, 1);
		\draw[blue](12, 4) -- (12, 1);
		\node[left, brown] at (9, 2.2) {$-hE_{+}$};
		\node[left, green] at (9, 1.5) {$hE_{-}$};
		\draw[brown] (9, 2) -- (9, 2.5);
		\draw[green] (9, 1) -- (9, 2);
		\node[right, blue] at (12, 3) {$sin(1+h)-sin(1)$};
		\node[above, blue] at (12, 4) {$A(1, sin(1))$};
                \node[below, blue] at (9, 1) {$B(1-h, sin(1-h))$};
		\node[right, blue] at (12, 2) {$2sin(1) - sin(1-h)-sin(1+h)$};
		\node[above, blue] at (8.5, 3) {\small{$C(1-h, 2sin(1)-sin(1+h))$}};
		\draw[->] (8.5, 3)--(9, 2.5);
	\end{tikzpicture}
\end{figure}

\section*{II. Exercise 8.15}

The order of accuracy of each formula can be easily got by taylor expansion on $u\left( \overline{x}+h \right) $ and $u\left( \overline{x} - h \right) $, which is
\begin{equation*}
	\begin{split}
		E_{+} = D_{+}u\left( \overline{x} \right)-u'\left( \overline{x} \right) 
		&=\frac{u\left( \overline{x} + h \right) - u\left( \overline{x} \right)  }{h}-u'\left( \overline{x} \right) \\
		&=\frac{u\left( \overline{x} \right) + hu'\left( \overline{x}\right)
		+\mathrm{O}\left( h^2 \right) - u\left( \overline{x} \right)   }{h}
		-u'\left( \overline{x} \right) 
		=\mathrm{O}\left( h \right) \\
		E_{-} = D_{-}u\left( \overline{x} \right)-u'\left( \overline{x} \right) 
		&=\frac{u\left( \overline{x} \right) - u\left( \overline{x} - h \right)  }{h}
		-u'\left( \overline{x} \right) \\
		&=\frac{u\left( \overline{x} \right) 
	- \left[u\left( \overline{x} \right) - hu'\left( \overline{x} \right)+\mathrm{O}\left(h^2\right)   \right]}{h}
	-u'\left( \overline{x} \right)
		=\mathrm{O}\left( h \right)\\
		E_0 = D_0u\left( \overline{x} \right)-u'\left( \overline{x} \right) 
		&=\frac{u\left( \overline{x}+h \right) - u\left( \overline{x} - h \right)  }{2h}
		-u'\left( \overline{x} \right) \\
		&=\frac{\left[u\left( \overline{x} \right) +
			hu'\left( \overline{x} \right)+h^2u''\left( \overline{x} \right) + \mathrm{O}\left( h^{3} \right)\right] 
		-\left[u\left(\overline{x}\right) - hu'\left( \overline{x} \right)+h^2u''\left( \overline{x} \right)
	+\mathrm{O}\left( h^{3} \right) \right]      }{2h} -u'\left( \overline{x} \right)
		=\mathrm{O}\left( h^2 \right).\\ 
	\end{split}
\end{equation*}
Thus we have deduced the order of accuracy of these formulas.

\section*{III. Exercise 8.16}
To get the solution in Example 8.12, we can deduce a quadratic polynomial p that satisfies 
$p\left( y \right) = u\left( y \right)$,where $y=\overline{x}$, $\overline{x}-h$ and $\overline{x}-2h$. 
Thus we can build a table of divided difference to derive the polynomial's coefficients, which is
\begin{center}
	\begin{tabular}{c|c c c c}	
		$\overline{x}-2h$&$u\left( \overline{x}-2h \right) $ &&\\
		$\overline{x} - h$ &$u\left( \overline{x} - h \right) $ &$\frac{u\left( \overline{x} - h \right) - u\left( \overline{x} - 2h \right)  }{h}$ &\\
		$\overline{x}$ &$u\left( \overline{x} \right) $ &
		$\frac{u\left( \overline{x} \right)-u\left( \overline{x} - h \right)  }{h}$ &
		$\frac{u\left( \overline{x} \right)+u\left( \overline{x} - 2h \right)-2u\left( \overline{x} - h \right)   }{2h^2}$.\\
	\end{tabular}
\end{center}
Thus we got the interpolating polynomial $p\left( x \right) $, which is
\begin{equation*}
	\begin{split}
		p\left( x \right)=&u\left( \overline{x}-2h \right)+\frac{u\left( \overline{x} - h \right)-u\left( \overline{x}-2h \right)  }{h}\left( x-\overline{x}+2h \right)
	+\frac{u\left( \overline{x} \right) +u\left( \overline{x}-2h \right)-2u\left( \overline{x}-h \right)   }{2h^2}\left( x-\overline{x}+2h \right)\left( x-\overline{x}+h \right)
.
\end{split}
\end{equation*}
Take derivative of the interpolating polynomial $p\left( x \right) $ to get the approximation to $u'\left( \overline{x} \right) $, we have
\begin{equation*}
	\begin{split}
		p'\left( \overline{x} \right)=&
		\frac{u\left( \overline{x}-h \right)-u\left( \overline{x}-2h \right)  }{h}
		+\frac{u\left( \overline{x} \right)+u\left( \overline{x}-2h \right)-2u\left( \overline{x}-h \right)   }{2h^{2}}\left( h+2h \right)\\
		=&\frac{3}{2h}u\left( \overline{x} \right)-\frac{2}{h}u\left( \overline{x}-h \right)+\frac{1}{2h}u\left( \overline{x}-2h \right).\\   
	\end{split}
\end{equation*}
The solution is the same as the FD formula $D_2u\left( \overline{x} \right) $ in Example 8.12.

\section*{Exercise 8.20}
We can easily get the results by the definition 8.19 and the definition of the operator $\mathrm{O}$.
\begin{equation*}
	\begin{split}
		\mid  \mid g \mid  \mid_\infty &=max_{i=1}^{N} \mid g_i \mid =\mathrm{O}\left( h \right)\\
		\mid  \mid g \mid  \mid_1&=h\sum_{i=1}^{N} \mid g_i \mid 
		=h\left( N-2 \right) \mathrm{O}\left( h^2\right)
		+2h\mathrm{O}\left( h \right)
		=\mathrm{O}\left( h^2 \right)-2\mathrm{O}\left( h^{3} \right) +2h\mathrm{O}\left( h \right)
		=\mathrm{O}\left( h^2 \right) \\	
		\mid  \mid g \mid  \mid_2&=\left( h\sum_{i=1}^{N} \mid g_i \mid^2 \right)^{\frac{1}{2}}
		=h^{\frac{1}{2}}\left[2\mathrm{O}\left( h^2 \right)+\left( N-2 \right)\mathrm{O}\left( h^{4} \right)   \right]^{\frac{1}{2}}
		=h^{\frac{1}{2}}[\mathrm{O}\left( h^2 \right)+\mathrm{O}\left( h^{3} \right)-2\mathrm{O}\left( h^{4} \right)   ]^{\frac{1}{2}}
		=\mathrm{O}\left( h^{\frac{3}{2}} \right).\\  
	\end{split}
\end{equation*}

The equation about infinit norm is achieved by the fact that when h is sufficiently small,
the elements with high order will be smaller than the one with lower order based on the standard norm on $\mathbb{R}$.
\section*{Exercise 8.44 Denote $B_E=A_E^{-1}$. Show that the first column of $B_E$ contains elements that are $\mathrm{O}\left( 1 \right) $}
Firstly, we deduce the Green's function that solves the function
\[
	\left\{
		\begin{array}{c}
			u''\left( x \right)=\delta\left( x-\overline{x} \right),\\
			u'\left( 0 \right)=u\left(1  \right)=0.\\ 
		\end{array}
		\right.
\] 
Like what we have done in the proof of Lemma 8.37, we have
\[
	\int_{x_0-\epsilon}^{x_0+\epsilon}G''\left( x \right)dx=
	\int_{x_0-\epsilon}^{x_0+\epsilon}\delta\left( x-\overline{x} \right)dx
	=\left\{
		\begin{array}{l l}
			0,&\overline{x}\notin\left( x_0-\epsilon,x_0+\epsilon \right)\\
			1,&\overline{x}\in\left( x_0-\epsilon,x_0+\epsilon \right)\\
		\end{array}
		\right.
.\]
The  fundamental theorem of calculus yields
\[
	\lim_{\epsilon\to 0}G'\left( x_0+\epsilon \right)-\lim_{\epsilon\to 0}G'\left( x_0-\epsilon \right)
	=\left\{
		\begin{array}{l l}
			0,&x_0\in\left( 0,\overline{x} \right)\cup\left( \overline{x}, 1 \right)\\
			1,&x_0=\overline{x}\\
		\end{array}
		\right.
.\] 
\begin{equation*}
	G\left( x; \overline{x}\right)=
	\left\{
		\begin{array}{c}
			ax+b,\quad x \in \left[0, \overline{x}\right],\\
			cx+d,\quad x \in \left[\overline{x}, 1\right].\\
		\end{array}
		\right.
\end{equation*}
From the given conditions and continuity, we can deduce the values of $a, b, c, d$. 
\[
	\left\{
		\begin{array}{l}
			c=a+1\\
			a=0\\
			a \overline{x}+b=c \overline{x}+d\\
			c+d=0\\
		\end{array}
	\right.
	\Rightarrow
	\left\{
		\begin{array}{l}
			a=0\\
			b=\overline{x}-1\\
			c=1\\
			d=-1\\
		\end{array}
	\right.		
.\] 
Thus we have 
 \[
	 G\left( x, \overline{x} \right)=
	 \left\{
		 \begin{array}{c}
			 \overline{x}-1\quad\left[0, \overline{x}\right],\\
			 x-1\quad\left[\overline{x}, 1\right].\\
		 \end{array}
		 \right.
\]
In the same way, we can deduce the function $G_0\left( x \right)=x-1 $ that solves 
\[
	\left\{
		\begin{array}{c}
			u''\left( x \right)=0,\\
			u'\left( 0 \right)=1, u\left( 1 \right)=0\\  
		\end{array}
		\right.
\]
and the function $G_1\left( x \right)=1 $ that solves
\[
\left\{
	\begin{array}{c}
		u''\left( x \right)=0,\\
		u'\left( 0 \right)=0, u\left( 1\right)=1.\\  
	\end{array}
	\right.
\] 
Then for the function
\[
\left\{
	\begin{array}{c}
		u''\left( x \right)=f\left( x \right) ,\\
		u'\left( 0\right)=\alpha, u\left( 1 \right)=\beta,\\  
	\end{array}
	\right.
,\]
the solution is $\alpha G_0\left( x \right)+\beta G_1\left( x \right)+
\int_0^{1}f\left( \overline{x} \right)G\left( x,\overline{x} \right)d\overline{x}    $.
Now we can easily deduce the inverse of $A_E$ by the Green functions.
\[
B=
\left[
	\begin{array}{c c c c c}
		x_0-1&h\left( x_1-1 \right)&h\left( x_2-1 \right)&\ldots&1\\
		x_1-1&h\left( x_1-1 \right)&h\left( x_2-1 \right)& \ldots&1\\
		x_2-1&h\left( x_2-1 \right)&h\left( x_2-1 \right)&\ldots&1\\
		\vdots&\vdots&\vdots&\ddots&\vdots\\
		x_{m+1}-1&h\left( x_{m+1}-1 \right)&h\left( x_{m+1 }-1 \right)&\ldots&1\\   
	\end{array}
\right]	
,\] 
where $x_i=ih$, $h=\frac{1}{m+1}$.
We denote $A_E=[a_0, a_1,\ldots,a_{m+1}]^{T}$ and $B=[b_0,b_1,\ldots,b_{m+1}]$, where $a_i$'s and $b_i$'s are vectors with length of $m+1$.
Calculate each element in $A_EB$, we have
\begin{equation*}
	\begin{split}
		a_0^{T}b_0&=-\frac{1}{h}x_0+\frac{1}{h}+\frac{1}{h}x_1-\frac{1}{h}=\frac{1}{h}h=1\\
		a_i^{T}b_0&=\frac{1}{h^2}\left(x_{i-1}-1-2x_{i}+2+x_{i+1}-1\right)=0\qquad i=1,\ldots, m\\
		a_{m+1}^{T}b_0&=x_{m+1}-1=0\\
		a_0^{T}b_j&=-x_j+1+x_j-1 =0\qquad j=1,\ldots, m\\
		a_{i}^{T}b_j&=\frac{1}{h}\left(x_j-1-2x_j+2+x_j-1\right)=0\qquad i=1,\ldots,m-1\quad i<j\le m\\
		a_{i}^{T}b_j&=\frac{1}{h}\left( x_{j}-1-2x_j+2+x_{j+1}-1 \right)=\frac{1}{h}h=1 \qquad i=1,\ldots,m\quad j=i\\
		a_{i}^{T}b_{j}&=\frac{1}{h}\left( x_{i-1}-1-2x_{i}+2+x_{i+1}-1 \right)=0\qquad j=1,\ldots,m-1 \quad j<i\le m\\
		a_{m+1}^{T}b_j&=h\left( x_{m+1}-1 \right)=0\qquad j=1,\ldots,m\\
		a_{0}^{T}b_{m+1}&=-\frac{1}{h}+\frac{1}{h}=0\\
		a_{i}^{T}b_{m+1}&=\frac{1}{h^2}\left( 1-2+1 \right) =0\qquad i=1,\ldots,m\\
		a_{m+1}^{T}b_{m+1}&=1.\\
	\end{split}
\end{equation*} 
Thus we have proved that $A_EB=I$. And we can easily find that each element in $b_0$ is $x_i-1=\mathrm{O}\left( 1 \right) $.
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
